package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.Arrays;

class GetMaximumInGeneratedArray {
    // 2022-09-02 13:54:27
    public static void main(String[] args) {
        Solution solution = new GetMaximumInGeneratedArray().new Solution();
        solution.getMaximumGenerated(7);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int getMaximumGenerated(int n) {
            if (n == 0) return 0;
            if (n == 1) return 1;
            int[] ans = new int[n + 1];

            ans[0] = 0;
            ans[1] = 1;

            int max = 0;
            for (int i = 2; i < ans.length; i++) {
                if (i % 2 == 0) {
                    ans[i] = ans[i / 2];
                } else {
                    ans[i] = ans[i / 2 + 1] + ans[i / 2];
                }
                max = Math.max(max, ans[i]);
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}